package com.zyk.leetcode;

import com.zyk.util.TreeUtil;

/**
 * @author zhangsan
 * @date 2021/5/7 11:49
 */
public class M1712 {


    //中序 对左节点玩左旋
    public static TreeNode convertBiNode(TreeNode root) {
        if (root == null) return null;
        return process(root, null);
    }

    // 中序做
    public static TreeNode process(TreeNode cur, TreeNode pre) {
        if(cur.left == null)
            return cur;
        process(cur.left, cur);
        // 操作
        pre.left = rightRotate(cur);

        process(cur.right, cur);
        return pre;
    }

    // 右旋, 返回新头
    public static TreeNode rightRotate(TreeNode cur) {
        TreeNode left = cur.left;
        cur.left = left.right;
        left.right = cur;
        return left;
    }


    // for test
    public static void main(String[] args) {
        Integer[] arr = {4, 2, 5, 1, 3, null, 6, 0};
        TreeNode root = TreeUtil.generateTreeByArr(arr);
        TreeNode newRoot = convertBiNode(root);
        while (newRoot != null) {
            System.out.println(newRoot.val);
            newRoot = newRoot.right;
        }
    }

}
